Demand%2DDriven Tag Recommendation.
Abstract. Collaborative tagging allows users to assign arbitrary keywords (or tags) describing the content of objects, which facilitates navigation and improves searching without dependence on pre-configured categories. In large-scale tagbased systems, tag recommendation services can assist a user in the assignment of tags to objects and help consolidate the vocabulary of tags across users. A promising approach for tag recommendation is to exploit the co-occurrence of tags. However, these methods are challenged by the huge size of the tag vocabulary, either because (1) the computational complexity may increase exponentially with the number of tags or (2) the score associated with each tag may become distorted since different tags may operate in different scales and the scores are not directly comparable. In this paper we propose a novel method that recommends tags on a demand-driven basis according to an initial set of tags applied to an object. It reduces the space of possible solutions, so that its complexity increases polynomially with the size of the tag vocabulary. Further, the score of each tag is calibrated using an entropy minimization approach which corrects possible distortions and provides more precise recommendations. We conducted a systematic evaluation of the proposed method using three types of media: audio, bookmarks and video. The experimental results show that the proposed method is fast and boosts recommendation quality on different experimental scenarios. For instance, in the case of a popular audio site it provides improvements in precision (p@5) ranging from 6.4 % to 46.7 % (depending on the number of tags given as input), outperforming a recently proposed co-occurrence based tag recommendation method. 1
Active Learning Genetic programming for record deduplication.
Abstract — The great majority of genetic programming (GP) algorithms that deal with the classification problem follow a supervised approach, i.e., they consider that all fitness cases available to evaluate their models are labeled. However, in certain application domains, a lot of human effort is required to label training data, and methods following a semi-supervised approach might be more appropriate. This is because they significantly reduce the time required for data labeling while maintaining acceptable accuracy rates. This paper presents the Active Learning GP (AGP), a semi-supervised GP, and instantiates it for the data deduplication problem. AGP uses an active learning approach in which a committee of multi-attribute functions votes for classifying record pairs as duplicates or not. When the committee majority voting is not enough to predict the class of the data pairs, a user is called to solve the conflict. The method was applied to three datasets and compared to two other deduplication methods. Results show that AGP guarantees the quality of the deduplication while reducing the number of labeled examples needed. I.
ONDUX on%2Ddemand unsupervised learning for information extraction.

A Self%2DSupervised Approach for Extraction of Attribute%2DValue Pairs from Wikipedia Articles.

Exploring features for the automatic identification of user goals in web search.

Classifying documents with link%2Dbased bibliometric measures.

Modeling the web as a hypergraph to compute page reputation.

Using structural information to improve search in Web collections.

Editorial.
calls &amp; calendarEDITORIAL
Using Statistical Features to Find Phrasal Terms in Text Collections.

A Probabilistic Approach for Automatically Filling Form%2DBased Web Interfaces.

Evidence of quality of textual features on the web 2.0.

Automatically filling form%2Dbased web interfaces with free text inputs.

Indexing the Web.
In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24 million pages is available at http://google.stanford.edu/

To engineer a search engine is a challenging task. Search engines index tens to hundreds of millions of web pages involving a comparable number of distinct terms. They answer tens of millions of queries every day. Despite the importance of large-scale search engines on the web, very little academic research has been done on them. Furthermore, due to rapid advance in technology and web proliferation, creating a web search engine today is very different from three years ago. This paper provides an in-depth description of our large-scale web search engine -- the first such detailed public description we know of to date.

Apart from the problems of scaling traditional search techniques to data of this magnitude, there are new technical challenges involved with using the additional information present in hypertext to produce better search results. This paper addresses this question of how to build a practical large-scale system which can exploit the additional information present in hypertext. Also we look at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
Inverted Files.
Research into inverted file compression has focused on compression ratio---how small the indexes can be. Compression ratio is important for fast interactive searching. It is taken as read, the smaller the index, the faster the search.
Text Indexing Techniques.
This paper presents recent work on a multimedia retrieval project at Cambridge University and Olivetti Research Limited (ORL). We present novel techniques that allow ex- tremely rapid audio indexing, at rates approaching several thousand times real time. Unlike other methods, these techniques do not depend on a fixed vocabulary recognition system or on keywords that must be known well in advance. Using statistical methods developed for text, these indexing techniques allow rapid and efficient retrieval and browsing of audio and video documents. This paper presents the project background, the indexing and retrieval techniques, and a video mail retrieval application incorporating content-based audio indexing, retrieval, and browsing.
An evolutionary approach for combining different sources of evidence in search engines.

A strategy for allowing meaningful and comparable scores in approximate matching.

A flexible approach for extracting metadata from bibliographic citations.

On Finding Templates on Web Collections.

Research Developments in Web Information Retrieval from Two Brazilian Universities.

Locality%2DBased pruning methods for web search.

Structure%2DBased Crawling in the Hidden Web.

Computing block importance for searching on web sites.

A strategy for allowing meaningful and comparable scores in approximate matching.

FLUX%2DCIM flexible unsupervised extraction of citation metadata.

A Hypergraph Model for Computing Page Reputation on Web Collections.
Abstract. In this work we propose a representation of the web as a directed hypergraph, instead of a graph, where links can connect not only pairs of pages, but also pairs of disjoint sets of pages. In our model, the web hypergraph is derived from the web graph by dividing the set of pages into non-overlapping blocks and using the links between pages of distinct blocks to create hyperarcs. Each hyperarc connects a block of pages to a single page and is created with the goal of providing more reliable information for link analysis methods. We used the hypergraph structure to compute the reputation of web pages by experimenting hypergraph versions of two previously proposed link analysis methods, Pagerank and Indegree. We present experiments which indicate the hypergraph versions of Pagerank and Indegree produce better results when compared to their original graph versions. 1.
An approach to XML path matching.

A cost%2Deffective method for detecting web site replicas on search engine databases.



A fast and robust method for web page template detection and removal.

A comparative study of citations and links in document classification.
It is well known that links are an important source of information when dealing with Web collections. However, the question remains on whether the same techniques that are used on the Web can be applied to collections of documents containing citations between scientific papers. In this work we present a comparative study of digital library citations and Web links, in the context of automatic text classification. We show that there are in fact differences between citations and links in this context. For the comparison, we run a series of experiments using a digital library of computer science papers and a Web directory. In our reference collections, measures based on co-citation tend to perform better for pages in the Web directory, with gains up to 37 % over text based classifiers, while measures based on bibliographic coupling perform better in a digital library. We also propose a simple and effective way of combining a traditional text based classifier with a citation-link based classifier. This combination is based on the notion of classifier reliability and presented gains of up to 14 % in micro-averaged F1 in the Web collection. However, no significant gain was obtained in the digital library. Finally, a user study was performed to further investigate the causes for these results. We discovered that misclassifications by the citation-link based classifiers are in fact difficult cases, hard to classify even for humans.
Extracting and Searching Useful Information Available on Web FAQs.

YAQCX A Word%2Dbased Query%2Daware Compressor for XML Data.
Abstract. XML has become a de facto standard for data exchanging over the Internet. However, efficiently storing and querying XML data isstill an open problem. In this paper we present YAQCX, Yet AnotherQuery-aware Compressor for XML. YAQCX adopts word-based modeling combined with byte-coding to provide a very efficient approach to compressing/decompressing and querying XML data. It also implements a subset of XPath with apowerful pattern matching extension that allows regular expressions, range queries, and partial matching. Additionally, when processing queries, it accesses the actual compressed data asfewaspossible, for example to solve predicates on contents or to show results. Based on our experiments, we show that YAQCX compression ratios are comparable to XMill’s and very close to those of other query-aware compressors, such as XQzip and XGrind. Wealso show that YAQCX compresses and decompresses faster than XMill, and outperforms XGrind regarding query processing. 1.
Structure%2Ddriven crawler generation by example.

GoGetIt%21 a tool for generating structure%2Ddriven web crawlers.

Site level noise removal for search engines.
The currently booming search engine industry has determined many online organizations to attempt to artificially increase their ranking in order to attract more visitors to their web sites. In the same time, the growth of the web has also inherently generated several  navigational hyperlink structures which have a negative impact on the importance measures employed by current search engines. In this paper we propose and evaluate algorithms for identifying all these noisy links over the web graph, may them be spam or simple relationships between real world entities represented by sites, replication  of content, etc. Unlike prior work, we target a different type of noisy link structures, residing at the site level, instead of the page level. We thus investigate and annihilate site level mutual reinforcement  relationships, abnormal support coming from one site towards another, as well as complex link alliances between web sites. Our experiments with the link database of the TodoBR search engine show a very strong increase in the quality of the output rankings after having applied our techniques.
Link%2Dbased similarity measures for the classification of Web documents.

SNIF A Simple Nude Image Finder.

Detec%E7%E3o de R%E9plicas Utilizando Conte%FAdo e Estrutura.

Impedance coupling in content%2Dtargeted advertising.

Application of Clustering Technique in Multiple Sequence Alignment.

Improving Web search efficiency via a locality based static pruning method.
The unarguably fast, and continuous, growth of the volume of indexed (and indexable) documents on the Web poses a great challenge for search engines. This is true regarding not only search e#ectiveness but also time and space e#- ciency. In this paper we present an index pruning technique targeted for search engines that addresses the latter issue without disconsidering the former. To this e#ect, we adopt a new pruning strategy capable of greatly reducing the size of search engine indices. Experiments using a real search engine show that our technique can reduce the indices&#039; storage costs by up to 60% over traditional lossless compression methods, while keeping the loss in retrieval precision to a minimum. When compared to the indices size with no compression at all, the compression rate is higher than 88%, i.e., less than one eighth of the original size. More importantly, our results indicate that, due to the reduction in storage overhead, query processing time can be reduced to nearly 65% of the original time, with no loss in average precision. The new method yields significative improvements when compared against the best known static pruning method for search engine indices. In addition, since our technique is orthogonal to the underlying search algorithms, it can be adopted by virtually any search engine.
Measuring similarity between collection of values.
In this paper, we propose a set of similarity metrics for manipulating collections of values occuring in XML documents. Following the data model presented in TAX algebra, we treat an XML element as a labeled ordered rooted tree. Consider that XML nodes can be either atomic, i.e, they may contain single values such as short character strings, date, etc, or complex, i.e., nested structures that contain other nodes, we propose two types of similarity metrics: MAVs, for atomic nodes and MCVs, for complex nodes. In the first case, we suggest the use of several application domain dependent metrics. In the second case, we define metrics for complex values that are structure dependent, andcanbe distinctly applied for tuples and collections of values. We also present experiments showing the effectiveness of our method.
Discovering Search Engine Related Queries Using Association Rules.
0 andar- Pampulha Belo Horizonte, Brazil
String Processing and Information Retrieval
Abstract. Given a sequence S = s1s2... sn of integers smaller than r = O(polylog(n)), we show how S can be represented using nH0(S) + o(n) bits, so that we can know any sq, as well as answer rank and select queries on S, in constant time. H0(S) is the zero-order empirical entropy of S and nH0(S) provides an Information Theoretic lower bound to the bit storage of any sequence S via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in O(log r) time. For larger r, we can still represent S in nH0(S) + o(n log r) bits and answer queries in O(log r / log log n) time. Another contribution of this paper is to show how to combine our compressed representation of integer sequences with an existing compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet Σ. Namely, we design a variant of the FM-index that indexes a string T [1, n] within nHk(T) + o(n) bits of storage, where Hk(T) is the k-th order empirical entropy of T. This space bound holds simultaneously for all k ≤ α log |Σ | n, constant 0 &lt; α &lt; 1, and |Σ |  = O(polylog(n)). This index counts the occurrences of an arbitrary pattern P [1, p] as a substring of T in O(p) time; it locates each pattern occurrence in O(log 1+ε n) time, for any constant 0 &lt; ε &lt; 1; and it reports a text substring of length ℓ in O(ℓ + log 1+ε n) time.
Combining link%2Dbased and content%2Dbased methods for web document classification.

Using Association Rules to Discover Search Engines Related Queries.
This work presents a method for automatic generate suggestions of related queries submitted to Web search engines. The method extracts information from the log of past submitted  queries to search engines using algorithms for mining association rules. Experimental results were performed on a log containing more than 2.3 million queries submitted to a commercial searching engine giving correct suggestions in 90.5% of the top 5 suggestions presented for common queries extracted from a real log.
Link Information as a Similarity Measure in Web Classification.
Abstract. The objective of this paper is to study how the link structure of the Web can be used to derive a similarity measure between documents. We evaluate five different measures and determine how accurate they are in predicting the subject of Web pages. Experiments with a Web directory indicate that the use of links from external pages greatly increases the quality of the results. Gains as high as 45:9 points in F1 were obtained, when compared to a text-based classifier. Among the similarity measures tested in this work, co-citation presented the best performance in determining if two Web pages are related. This work provides an important insight on how similarity measures can be derived from links and applied to Web IR problems.
Local versus global link information in the Web.
 
Adding compression to next%2Dgeneration text retrieval systems.

Expans%E3o de Consultas Utilizando Indexa%E7%E3o Sem%E2ntica Latente.

Rank%2DPreserving Two%2DLevel Caching for Scalable Search Engines.

Constru%E7%E3o Eficiente de %CDndices para Bases de Dados Textuais.

Link%2Dbased and content%2Dbased evidential information in a belief network model.

Fast and flexible word searching on compressed text.
text. When searching complex or approximate patterns, our algorithms are up to 8 times faster than the search on uncompressed text. We also discuss the impact of our technique in inverted files pointing to logical blocks and argue for the possibility of keeping the text compressed all the time, decompressing only for displaying purposes. Categories and Subject Descriptors: E.4 [Coding and Information Theory]: Data Compaction This work has been partially supported by SIAM Project, grant MCT/FINEP/PRONEX 76.97.1016.00, AMYRI/CYTED Project, CAPES scholarship (E. S. de Moura), Fondecyt grant 1990627 (G. Navarro and R. Baeza-Yates) and CNPq grant 520916/94-8 (N. Ziviani).  Authors&#039; addresses: E. S. de Moura and N. Ziviani, Dept. of Computer Science, Univ. Federal de Minas Gerais, Av. Antonio Carlos 6627, Belo Horizonte, Brazil; G. Navarro and R. Baeza-Yates, Dept. of Computer Science, Univ. de Chile, Av. Blanco Encalada 2120, Santiago, Chile.  Permission to make digital or h
Compression A Key for Next%2DGeneration Text Retrieval Systems.
In this article we discuss recent methods for compressing the text and the index of text retrieval systems. By compressing both the complete text and the index, the total amount of space is less than half the size of the original text alone. Most surprisingly, the time required to build the index and also to answer a query is much less than if the index and text had not been compressed. This is one of the few cases where there is no space-time trade-off. Moreover, the text can be kept compressed all the time, allowing updates when changes occur in the compressed text.
Adding Compression to Block Addressing Inverted Indexes.
. Inverted index compression, block addressing and sequential search on compressed text are three techniques that have been separately developed for efficient, low-overhead text retrieval. Modern text compression techniques can reduce the text to less than 30% of its size and allow searching it directly and faster than the uncompressed text. Inverted index compression obtains significant reduction of their original size at the same processing speed. Block addressing makes the inverted lists point to text blocks instead of exact positions and pay the reduction in space with some sequential text scanning.  In this work we combine the three ideas in a single scheme. We present a compressed inverted file that indexes compressed text and uses block addressing. We consider different techniques to compress the index and study their performance with respect to the block size. We compare the index against three separate techniques for varying block sizes, showing that our index is superior to each isolated approach. For instance, with just 4% of extra space overhead the index has to scan less than 12% of the text for exact searches and about 20% allowing one error in the matches. Keywords: Text compression, inverted files, block addressing, text databases.  1. 
Efficient Distributed Algorithms to Build Inverted Files.
1 Introduction The potential large size of a full text collection demands specialized indexing techniques for efficient retrieval. Some examples of such indexes are suffix arrays, inverted files, and signature files. Each of them have their own strong and weak points. However, inverted files have been traditionally the most popular indexing technique used along the years. Inverted files are useful because their searching strategy is based mostly on the vocabulary which usually fits in main memory. Further, inverted files are simple to update and perform well when the pattern to be searched for is formed by conjunctions and disjunctions of simple words, a common type of query in IR systems and in the Web. Despite their simple structure, the task of building inverted files for very large text collections such as the whole Web is costly. Therefore, faster indexing algorithms are always desirable and the use of parallel or distributed hardware for generating the index is an obvious alternative. In this regard, as hardware platform we consider a network of workstations because it presents performance comparable to that of a typical parallel machine but is more cost effective [1, 4].
Efficient Distributed Algorithms to Build Inverted Files.
1 Introduction The potential large size of a full text collection demands specialized indexing techniques for efficient retrieval. Some examples of such indexes are suffix arrays, inverted files, and signature files. Each of them have their own strong and weak points. However, inverted files have been traditionally the most popular indexing technique used along the years. Inverted files are useful because their searching strategy is based mostly on the vocabulary which usually fits in main memory. Further, inverted files are simple to update and perform well when the pattern to be searched for is formed by conjunctions and disjunctions of simple words, a common type of query in IR systems and in the Web. Despite their simple structure, the task of building inverted files for very large text collections such as the whole Web is costly. Therefore, faster indexing algorithms are always desirable and the use of parallel or distributed hardware for generating the index is an obvious alternative. In this regard, as hardware platform we consider a network of workstations because it presents performance comparable to that of a typical parallel machine but is more cost effective [1, 4].
Linear Time Sorting of Skewed Distributions.

Fast Searching on Compressed Text Allowing Errors.
We present a fast compression and decompression scheme for natural language texts that allows efficient and flexible string matching by searching the compressed text directly. The compression scheme uses a word-based Huffman encoding and the coding alphabet is byte-oriented rather than bit-oriented. We compress typical English texts to about 30% of their original size, against 40% and 35% for Compress and Gzip, respectively. Compression times are close to the times of Compress and approximately half the times of Gzip, and decompression times are lower than those of Gzip and one third of those of Compress.  The searching algorithm allows a large number of variations of the exact and approximate compressed string matching problem, such as phrases, ranges, complements, wild cards and arbitrary regular expressions. Separators and stopwords can be discarded at search time without significantly increasing the cost. The algorithm is based on a word-oriented shift-or algorithm and a fast Boyer-Moore-type filter. It concomitantly uses the vocabulary of the text available as part of the Huffman coding data. When searching for simple patterns, our experiments show that running our algorithm on a compressed text is twice as fast as running Agrep on the uncompressed version of the same text. When searching complex or approximate patterns, our algorithm is up to 8 times faster than Agrep. We also mention the impact of our technique in inverted files pointing to documents or logical blocks as Glimpse.   
Direct Pattern Matching on Compressed Text.
We present a fast compression and decompression technique for natural language texts. The novelty is that the exact search can be done on the compressed text directly, using any known sequential pattern matching algorithm. Approximate search can also be done efficiently without any decoding. The compression scheme uses a semi-static word-based modeling and a Huffman coding where the coding alphabet is byte-oriented rather than bit-oriented. We use the first bit of each byte to mark the beginning of a word, which allows the searching of the compressed pattern directly on the compressed text. We achieve about 33% compression ratio for typical English texts. When searching for simple patterns, our experiments show that running our algorithm on a compressed text is almost twice as fast as running agrep on the uncompressed version of the same text. When searching complex or approximate patterns, our algorithm is up to 8 times faster than agrep.
